package leetcode_classic150;

import java.util.*;

@SuppressWarnings("all")
public class Demo6 {


    //  128. 最长连续序列
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);

        int res = 0;
        for (Integer x : set) {
            if (set.contains(x - 1)) continue;

            int count = 0;
            for (Integer i = x; set.contains(x); x++) count++;
            res = Math.max(res, count);
        }
        return res;
    }


    // 502. IPO
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        Integer[] index = new Integer[n];
        for (Integer i = 0; i < n; i++) index[i] = i;
        Arrays.sort(index, (a, b) -> capital[a] - capital[b]);    // 按启动项目的最小资本从小到大排序


        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> profits[b] - profits[a]);    // 将项目纯利润按从大到小排序
        int ret = w, i = 0;
        while (i < n && ret >= capital[index[i]]) maxHeap.add(index[i++]);
        while (k-- > 0 && !maxHeap.isEmpty()) {
            ret += profits[maxHeap.poll()];
            while (i < n && ret >= capital[index[i]]) maxHeap.add(index[i++]);
        }
        return ret;
    }


    //
    // 215. 数组中的第K个最大元素
    public int findKthLargest(int[] nums, int k) {
        // 方法一： 快速选择
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        int index = left + new Random().nextInt(right - left + 1);
        int pivot = nums[index];
        // [l, cur]: <pivot   [left + 1, cur] == pivot  [r, right]: >pivot
        int l = left - 1, r = right + 1, cur = left;
        while (cur < r) {
            if (nums[cur] == pivot) cur++;
            else if (nums[cur] > pivot) swap(nums, ++l, cur++);
            else swap(nums, cur, --r);
        }
        int a = l - left + 1, b = r - l - 1, c = right - r + 1;
        if (k <= a) return quickSelect(nums, left, l, k);
        else if (k > a && k <= a + b) return pivot;
        return quickSelect(nums, r, right, k - a - b);
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


    // 295. 数据流的中位数
    class MedianFinder {
        PriorityQueue<Integer> minHeap;
        PriorityQueue<Integer> maxHeap;

        public MedianFinder() {
            minHeap = new PriorityQueue<>();
            maxHeap = new PriorityQueue<>((a, b) -> b - a);
        }

        public void addNum(int num) {
            if (maxHeap.size() == minHeap.size()) {
                if (maxHeap.isEmpty() || num <= minHeap.peek()) maxHeap.add(num);
                else {
                    maxHeap.add(minHeap.poll());
                    minHeap.add(num);
                }
                return;
            }

            if (num >= maxHeap.peek()) minHeap.add(num);
            else {
                minHeap.add(maxHeap.poll());
                maxHeap.add(num);
            }
        }

        public double findMedian() {
            if (maxHeap.size() > minHeap.size()) return (double) maxHeap.peek();
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }




    // 73. 矩阵置零
    public void setZeroes(int[][] matrix) {
        // 空间复杂度：O(1)
        int n = matrix.length, m = matrix[0].length;
        boolean row = false, col = false;

        // 1. 先确定首行和首列是否会被置零
        for (int i = 0; i < n; i++) {
            if (matrix[i][0] == 0) {
                col = true;
                break;
            }
        }
        for (int j = 0; j < m; j++) {
            if (matrix[0][j] == 0) {
                row = true;
                break;
            }
        }

        // 2. 确定被置零的行和列
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
            }
        }

        // 3. 开始置零
        for (int i = 1; i < n; i++) {
            if (matrix[i][0] == 0) Arrays.fill(matrix[i], 0);
        }
        for (int j = 1; j < m; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 0; i < n; i++) matrix[i][j] = 0;
            }
        }

        // 若 row 或 col 为 true，则置零
        if (row) Arrays.fill(matrix[0], 0);
        if (col) for (int i = 0; i < n; i++) matrix[i][0] = 0;
    }




    // 4. 寻找两个正序数组的中位数
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int len = (m + n) / 2 + 1;
        int[] tmp = new int[len];
        int k = 0, i = 0, j = 0;
        while (i < n && j < m && k < len) {
            if (nums1[i] <= nums2[j]) tmp[k++] = nums1[i++];
            else tmp[k++] = nums2[j++];
        }
        while (i < n && k < len) tmp[k++] = nums1[i++];
        while (j < m && k < len) tmp[k++] = nums2[j++];

        if ((m + n) % 2 == 0) return (tmp[len - 1] + tmp[len - 2]) / 2.0;
        return (double)tmp[len - 1];
    }



    // 67. 二进制求和
    public String addBinary(String a, String b) {
        int carry = 0;
        StringBuilder res = new StringBuilder();
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0 || carry > 0; ) {
            if (i >= 0) carry += a.charAt(i--) - '0';
            if (j >= 0) carry += b.charAt(j--) - '0';
            res.append((char)(carry % 2 + '0'));
            carry /= 2;
        }
        return res.reverse().toString();
    }



    // 191. 位1的个数
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            res++;
            n &= (n - 1);
        }
        return res;
    }


    // 136. 只出现一次的数字
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int x : nums) res ^= x;
        return res;
    }



    // 137. 只出现一次的数字 II
    public int singleNumber2(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;    // 保存每个数该比特位的和
            // 对于 sum = sum % 3, sum 总是与那个仅出现一次的元素的比特位值相同
            for (int j = 0; j < nums.length; j++) {
                sum += (nums[j]>>i) & 1;
            }
            if (sum % 3 == 1) res |= 1<<i;
        }
        return res;
    }


    // 69. x 的平方根
    public int mySqrt(int x) {
        if (x == 0) return 0;

        long left = 1, right = x, mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (mid * mid == x) return (int)mid;
            else if (mid * mid < x) left = mid + 1;
            else right = mid - 1;
        }
        return (int)right;
    }



    // 139. 单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        // 1. 统计字典中存在的单词
        Set<String> dictionary = new HashSet<>();
        dictionary.addAll(wordDict);

        // dp[j]: 以 i 位置为结尾的子串能否由字典中的单词拼接而出
        int n = s.length();
        s = " " + s;
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = i; j >= 1; j--) {
                String tmp = s.substring(j, i + 1);
                if (dp[j - 1] && dictionary.contains(tmp)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }



    // 322. 零钱兑换
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) dp[i] = 0X3f3f3f3f;

        for (int i = 1; i <= n; i++) {
            for (int j = coins[i - 1]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }

        return dp[amount] >= 0X3f3f3f3f ? -1 : dp[amount];
    }




    // 70. 爬楼梯
    public int climbStairs(int n) {
        int a = 1, b = 1, c = 1;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }


    // 64. 最小路径和
    public int minPathSum(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= m; i++) dp[0][i] = 0X3f3f3f3f;
        for (int i = 2; i <= n; i++) dp[i][0] = 0X3f3f3f3f;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[n][m];
    }


    // 63. 不同路径 II
    public int uniquePathsWithObstacles(int[][] og) {
        int n = og.length, m = og[0].length;

        int[][] dp = new int[n + 1][m + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (og[i - 1][j - 1] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[n][m];
    }




    // 300. 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int res = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }


    // 123. 买卖股票的最佳时机 III
    public int maxProfit(int[] prices) {
        // f[i][j]: 在前 i 只股票中完成 j 笔交易,且当天结束后交易状态为 持有股票   所能获取的最大利润
        // g[i][j]: 在前 i 只股票中完成 j 笔交易,且当天结束后交易状态为 未持有股票 所能获取的最大利润
        int n = prices.length, INF = 0x3f3f3f3f;
        int[][] f = new int[n][3], g = new int[n][3];
        for (int j = 1; j <= 2; j++) f[0][j] = g[0][j] = -INF;
        // 注意:这里 f[i][j]只能初始化第一天,因为后面可能买别的股票,但没有卖出
        f[0][0] = -prices[0];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= 2; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j > 0) g[i][j] = Math.max(f[i - 1][j - 1] + prices[i], g[i][j]);
            }
        }

        int ret = -INF;
        for (int i = 0; i < 3; i++) {
            ret = Math.max(ret, g[n - 1][i]);
        }
        return ret;
    }


    // 188. 买卖股票的最佳时机 IV
    public int maxProfit(int k, int[] prices) {
        // f[i][j]: 在前 i 只股票中完成 j 笔交易,且当天结束后交易状态为 持有股票   所能获取的最大利润
        // g[i][j]: 在前 i 只股票中完成 j 笔交易,且当天结束后交易状态为 未持有股票 所能获取的最大利润
        int n = prices.length, INF = 0x3f3f3f3f;
        int[][] f = new int[n][k + 1], g = new int[n][k + 1];
        for (int j = 1; j <= k; j++) f[0][j] = g[0][j] = -INF;
        // 注意:这里 f[i][j]只能初始化第一天,因为后面可能买别的股票,但没有卖出
        f[0][0] = -prices[0];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j > 0) g[i][j] = Math.max(f[i - 1][j - 1] + prices[i], g[i][j]);
            }
        }

        int ret = -INF;
        for (int i = 0; i <= k; i++) {
            ret = Math.max(ret, g[n - 1][i]);
        }
        return ret;
    }



    // 5. 最长回文子串
    public String longestPalindrome(String s) {
        int n = s.length();
        int start = 0, end = 0;

        for(int i = 0; i < n - 1; i++) {
            int left = i - 1, right = i + 1;
            for( ; left >= 0 && right < n && s.charAt(left) == s.charAt(right); left--, right++);
            int tmpStart = left + 1, tmpEnd = right - 1;
            for(left = i, right = i + 1; left >= 0 && right < n && s.charAt(left) == s.charAt(right); left--, right++);

            if(right - left - 1 > tmpEnd - tmpStart + 1) {
                tmpStart = left + 1;
                tmpEnd = right - 1;
            }
            if(tmpEnd - tmpStart + 1 > end - start + 1) {
                start = tmpStart;
                end = tmpEnd;
            }
        }
        return s.substring(start, end + 1);
    }



    // 452. 用最少数量的箭引爆气球
    public int findMinArrowShots(int[][] points) {
        // 本质上为区间交集的最大个数
        // 1. 对一维数组下标为 0 的元素进行排序
        Arrays.sort(points, (a, b) -> {
            return a[0] > b[0] ? 1 : -1;
        });

        // 2. 求区间交集的个数
        int res = 1;
        int end = points[0][1], n = points.length;
        for (int i = 1; i < n; i++) {
            if (end >= points[i][0]) {
                end = Math.min(end, points[i][1]);
            } else {
                res++;
                end = points[i][1];
            }
        }
        return res;
    }
}
